package com.linchong.sort;

/**
 * @BelongsProject:Algorithm
 * @BelongsPackage:com.linchong.sort
 * @Author:linchong
 * @CreateTime:2019-01-04 22:12
 * @Description:堆排序
 * 步骤：
 *      1.建堆:O(n)
 *      2.排序:O(logn)
 *  最好、最坏、平均时间复杂度：O(nlogn),
 *  空间复杂度：O(1)
 *  是否稳定：不稳定
 *  是否受初始化数据影响：不受
 *
 *
 */
public class HeapSort {

    //建堆,自底向上
    public static void buildHeap(int[] arr,int n){
        for(int i = n/2; i >= 0;i--){
            System.out.println(" i = " + i);
            heapify(arr,n,i);
            for (int i1 : arr) {
                System.out.print(" ---> "+i1);
            }
            System.out.println();
        }
    }

    //堆化
    private static void heapify(int[] arr, int n, int i) {
        while(true) {
            int maxPos = i;
            if(2*i<=n&&arr[i*2]>arr[i]) maxPos = 2*i;
            if(2*i+1<=n&&arr[i*2+1]>arr[maxPos]) maxPos = 2*i+1;
            swap(arr,i,maxPos); //i上存放最大值
            if(i == maxPos) break;
            i = maxPos;
        }
    }

    public static void sort(int[] arr,int n){
        buildHeap(arr,n);

        System.out.println();
        int k = n;
        while(k>=0){
            swap(arr,k,0);
            k--;
            heapify(arr,k,0);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        //int [] arr = {6,2,4,8,10 ,24,12};
        int [] arr = {4,7,2,5,8,9};
        sort(arr,arr.length-1);
        for (int i : arr) {
            System.out.print(" " + i);
        }
    }
}
